package week02;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 丑数
 *
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 *
 * 1 是丑数。
 * n 不超过1690。
 */
public class Code08 {

    public int nthUglyNumber(int n) {
        PriorityQueue<Long> heap = new PriorityQueue<>();
        Set<Long> existed = new HashSet<>();
        int[] factors = new int[] {2 ,3, 5};
        heap.add(1L);
        existed.add(1L);
        int uglyNum = 0;
        for (int i = 0; i < n; i++) {
            long curNum = heap.poll();
            uglyNum = (int) curNum;
            for (int factor : factors) {
                long next = factor * curNum;
                if (existed.add(next)) {
                    heap.add(next);
                }
            }
        }
        return uglyNum;
    }
}
